Subject: Adaptive pacing patent, proposal

From: [email-masked]
Date: Thu, 27 Jan 94 12:34:17 EST

Fellow flow controllers,
IBM has decided NOT to make its patent titled "Adaptive Session-Level
Pacing" available to DLSw implementers on any special terms.  This
patent is available to APPN implementers as part of the APPN technology
package or through the normal IBM open patent licensing practice.

It seemed clear from the discussion in our September SIG meeting that
no one wanted a patent-dependent pacing solution, so I am assuming that
some features of the scheme I suggested months ago are now ruled out
as part of our DLSw standard flow control mechanism.  Although we may
have lost a little time considering some of that proposal's details,
I think you'll find that most of the discussions we had about it and
other proposals were not in vain.  We moved toward consensus on a number
of points and can now apply those to other flow control schemes.

With time getting short before our next meeting, I thought I would make
a new proposal so we have a specific scheme to discuss and don't lose
any more time on this issue.  I have made it closer to the VR-pacing-
based Wind/Kushi scheme but have clarified and completed the pacing
rules and added sections on capabilities exchange and management.
Perhaps most importantly, I have reviewed the pacing scheme with the
local IBM legal department and confirmed that it is not covered by any
patent they know about.  At the September meeting, others had thoughts
about the direction we should go if the patent decision was "no" -
please feel free to bring those ideas forward also .......

===============================
NEW DLSw FLOW CONTROL PROPOSAL:
===============================
(Numbers in parentheses refer to the NOTES section which follows)

CAPABILITY EXCHANGE - (1)
=========================
Four types of flow control capability are defined for a DLSw node:
  NONE  - The node does not send or receive any SSP flow control msgs.
  ONOFF - The node can receive ENTERBUSY and EXITBUSY and will stop and
          start sending I-frame and UI-frame traffic ASAP to the other
          router (xBUSY originator) on the specified circuit.  The node
          may also send ENTER/EXITBUSY.(2)
  FIXED - The node implements the send and receive sides of fixed pacing
          logic (described below) on a circuit basis.
  ADAPT - The node implements the send and receive sides of adaptive
          pacing logic (described below) on a circuit basis.(3)  This is
          a superset of FIXED.

To claim base level support of the DLSw standard, a node must implement
at least FIXED support.(4)  ADAPT support is optional and is above the
base.

Two DLSw partners establish through capability exchange the type of
flow control that will exist on all transport connections between those
two nodes.  A given node may simultaneously support different types of
flow control with different partners.  The same type of flow control
operates in both directions on circuits on a given transport connection.

As part of initial capability exchange, each node reports to the other
all the types of flow control it is capable of supporting.  Nodes which
do not support capability exchange are assumed to support only NONE.(5)
Nodes which support FIXED or ADAPT also specify the (initial) pacing win-
dow size they are expecting in their role as a traffic receiver.(6)  Both
nodes independently determine the flow control type that will exist
on their shared transport connection by choosing the highest level of flow
control that both nodes support (ADAPT > FIXED > ONOFF > NONE).  There is
no need for exchange of the result of this choice, since both nodes will
reach the same result.  If a node finds the result unacceptable (e.g., an
implementation is buffer-constrained so all partners must support at least
FIXED), it may take down the TCP connection.(7)

ADAPTIVE PACING -
=================
Flags/fields in the short ("information header"):
- Pacing Request Indicator  (PREQ) - 1 bit
- Pacing Response Indicator (PRSP) - 1 bit
- Increment Window Indicator (IWI) - 1 bit
- Halve Window Indicator     (HWI) - 1 bit
- Reset Window Indicator     (RWI) - 1 bit

New SSP message types:
IPM - simply the message type in the 16-byte information message header,
      with no fields following the header

Note that ENTERBUSY and EXITBUSY may be exchanged only under flow control
type ONOFF, and are not valid under type ADAPT or FIXED.

Function:
Pacing is done on a circuit basis only, in both directions independently.
The pacing receiver controls via a sliding cumulative window how many
frames a sender may put on the transport connection, for a given circuit.
Pacing is applied only to SSP message types INFOFRAME and DGRMFRAME.  The
point at which a DLSw node should RNR a data link or begin to discard
UI-frames is an implementation issue for the router and is not specified
by this pacing architecture.

The sender sets PREQ in the first frame of every window.  It may continue
to send the full window's worth of frames before it must stop and await a
pacing response.  When a pacing response is received, the sender adds the
current next window size (as adjusted by the just-received IWI or HWI) to
the current remaining window size to reach a new current window size.

The initial pacing window size = next window size for a circuit is
determined during capability exchange.  Each sender is obligated to
begin with the initial window size passed by its partner node (the
two values are independent).

In normal operation, the receiver receives I/UI-frames and looks for
a frame with PREQ set.  When it sees one, it determines based on
implementation-dependent conditions how to adjust the next window size and
when to send the pacing response (it could be withheld).(8)  The receiver
controls the window sizes it grants, and is not required to pre-allocate
buffer space for all the outstanding windows.

Solicited pacing responses (those sent in response to PREQ) may be sent
piggy-backed or as IPMs.  In either case, the pacing receiver sets PRSP
and one or neither of IWI and HWI.  Setting neither leaves the next window
size at its current value.  Setting IWI increments it by one, and setting
HWI sets it to MAX(FLOOR(current NWS / 2),1).

To respond quickly to congestion, the pacing receiver may send an unsoli-
cited "reset window" indication to the pacing sender.  This indication may
be sent only as an IPM (not piggy-backed), with PRSP=0 and RWI=1.  Upon
receipt of this message, the sender immediately ends the current window and
sets the next window size to 1.(9)  The sender must reflect the RWI bit back
along with PREQ in the first and only frame in the new window, to allow the
receiver to determine the end of the window outstanding at the time it sent
RWI.  An IPM with RWI resets a "PRSP owed" condition at both the pacing
sender and receiver, but the receiver must still treat the entire currently
granted window as outstanding until it receives PREQ+RWI back.(10)

The pacing receiver may in fact send an IPM with RWI in place of a regular
solicited pacing response, since it resets a "PRSP owed" condition.

FIXED PACING -
==============
Circuits running with FIXED flow control use the same formats and rules
as described for adaptive pacing, with the following simplifications:

- Pacing receivers cannot set IWI or HWI in solicited pacing responses.
- Pacing receivers cannot send unsolicited indications with RWI=1.
- Pacing senders do not have to support receipt of these messages.

Hence, the initial pacing window size and next window size at the sender are
always the same constant value set by the receiver during capabilities
exchange.  The only circuit-level mechanism a pacing receiver has to slow
down a sender is to withhold pacing responses.

MANAGEMENT CONSIDERATIONS -
===========================
The following are suggested fields for the "standard" DLSw MIB:
- all the flow control types supported by this node (get)
- as part of the partner list, the flow control type in operation for
  each transport connection (get)
- as part of the circuit list, the following values being maintained
  as a pacing sender:  current pacing window, current next window size (get)
- administrative state to cause circuit reset to initial pacing values (set)

NOTES:
======
1) I am assuming something like one subvector for flow control capabilities
   with subfields for what's supported and for initial pacing window
   count(s).  At the time of this writing I don't know if this sort of
   format or the idea of a single (non-negotiated) caps exchange matches
   what Wayne Clark is developing, but this is all changeable.
2) Sending xBUSY isn't required, but being able to receive them and act
   appropriately is required.  Note that the definition refers to stopping
   and starting traffic between the routers, and does not address when
   a router should RR/RNR the affected data link.  Perhaps the ONOFF
   definition should only refer to I-frames and not UI-frames;  this is
   a discussion that those vendors who can receive xBUSY need to have.
3) Receivers are actually not obligated to ever vary the pacing window
   size, but the sender must be able to respond correctly to window changes.
   That is, a valid ADAPT implementation may implement only the trivial
   logic of being an ADAPT sender without any of the sophistication
   required to intelligently set IWI, HWI, and RWI as a pacing receiver.
4) I feel ONOFF is significantly inferior to pacing because the OFF
   message can be delayed when it is most needed.  Defining ONOFF here
   allows the standard to address interoperation of products doing
   ENTER/EXITBUSY without each vendor of those products having to do
   their own vendor-unique code point.
5) I didn't think it was fair to default to ONOFF since ENTERBUSY and
   EXITBUSY weren't discussed in RFC 1434.  Those vendors who will have
   pre-standard DLSw implementations in the field need to discuss whether
   this is the best choice.
6) We probably need to allow for two different starting values, one
   for fixed and one for adaptive pacing.
7) I would support defining a Partner_Reject message so the two nodes
   can log this event and know not to keep retrying.  We could discuss
   this in the capabilities exchange siglet.
8) The receiver makes this determination with no knowledge of how well
   the sender is using the current window (there is no "request larger
   window" indicator).
9) We may want to revise the RWI definition to reset the window to 0
   rather than 1.  I made it 1 for now to reflect some of Shannon's
   earlier concerns with closing the window, plus to avoid the need
   for IPMs to flow both ways.  The effect of making it 1 is that
   implementers who want to shut off flow completely will have to
   buffer at least 1 frame per circuit in the pacing receiver before
   they will have a chance to withhold a pacing response.
10) It would actually be better to have the "reset ack" carried on an
    required IPM, so the receiver could free the window faster, but I
    did it this way for now for simplicity.  I am leaning toward
    changing this and also allowing window reset to 0, but I would
    like to hear others' opinions.

OTHER COMMENTS:
===============
- I have omitted a transport level start/stop protocol in this
  proposal for simplicity's sake.  I know we voted FOR such a protocol
  being in the BASE in the late afternoon session on flow control in
  September.  If, after some more e-mail discussion, we confirm that
  this is what we want, here's how one might fit it into the above
  scheme:
    - Define a special reserved Circuit ID value (all FFs?) that
      means "the transport connection" (not a specific circuit).
      We may want this for capabilities exchange anyway so the
      transport connection READ code can always deal with a short
      "information message" DLSw header at the start of all frames.
    - A node sends ENTERBUSY and EXITBUSY message types with the
      reserved circuit id, and the receiver must stop/start feeding
      I-frame and UI-frame traffic to the transport connection
      interface immediately.  This doesn't stop information already
      handed to the transport protocol stack.
    - Include in the definition of FIXED and ADAPT that a node must
      support receipt of ENTERBUSY and EXITBUSY at the transport
      connection level.

I guess that's it for the proposal.  I would like to get some proto-
typing done for the adaptive scheme to see how well it works;  I
think we all agreed in September this was needed before we really
adopt anything.  Any volunteers?  In the meantime, there are lots
of issues to be resolved, and I look forward to your comments.

Peter